home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Languages / Rewrite 0.2.6 / ReWrite 0.2.6 Docs / ReWrite 0.2.6 Docs.rsrc / TEXT_136.txt < prev    next >
Encoding:
Text File  |  1995-08-23  |  7.6 KB  |  191 lines
  1.  
  2. Chapter 8 - A bigger Example - nprime, atoi
  3.  
  4.    In this section we consider a particular example, that of finding the nth prime number.
  5.    At the end, the source (without documentation) for a string to integer function is given.
  6.  
  7. nprime
  8.  
  9. (The style used for code in this chapter is changed for purposes of readability)
  10.  
  11. This example finds the nth prime number, using the following method:
  12. - keep a list of all the primes we have found;
  13. - try each new number against the list we have found so far to see if prime;
  14.    (only need to check up to the square root of the number we are trying)
  15. - repeat until have enough primes.
  16.  
  17. (* we have a header here to get things started *)
  18. nprime[n:int] -> primeaux[{},0,n,2];
  19.  
  20. (* primeaux[primes found so far, sqrt of latest try, number to go, latest try *)
  21. (* none to go, so finished *)
  22. primeaux[l,s,0,k] -> k-1;
  23. (* update the square root *)
  24. primeaux[l,s,n,k]::k>s*s -> primeaux[l,s+1,n,k];
  25. (* see if we've found one *)
  26. primeaux[l,s,n,k]::primetest[l,s,k] -> primeaux[{.l,k},s,n-1,k+1];
  27. (* otherwise try the next *)
  28. primeaux[l,s,n,k] -> primeaux[l,s,n,k+1];
  29.  
  30. (* primetest[list to try dividing against, sqrt of latest try, number we are testing *)
  31. (* didn't divide any, therefore prime *)
  32. primetest[{},s,k] -> true;
  33. (* didn't divide any less than the square root, so prime *)
  34. primetest[{a,.b},s,k]::a>s -> true;
  35. (* a division, so not prime *)
  36. primetest[{a,.b},s,k]::k%a=0 -> false;
  37. (* didn't divide that number, try the next *)
  38. primetest[{a,.b},s,k] -> primetest[b,s,k];
  39.  
  40. nprime[2000] -> 17389
  41. Time taken on LC III: 8009 ticks.
  42.  
  43.     Here is the same code with types added (which speeds up all the arithmetic) and the comments removed.
  44.  
  45. nprime[n:int] -> primeaux[{},0,n,2];
  46.  
  47. primeaux[l:lis,s:int,0,k:int] -> k-1;
  48. primeaux[l:lis,s:int,n:int,k:int]::k>s*s -> primeaux[l,s+1,n,k];
  49. primeaux[l:lis,s:int,n:int,k:int]::primetest[l,s,k] -> primeaux[{.l,k},s,n-1,k+1];
  50. primeaux[l:lis,s:int,n:int,k:int] -> primeaux[l,s,n,k+1];
  51.  
  52. primetest[{},s:int,k:int] -> true;
  53. primetest[{a:int,.b},s:int,k:int]::a>s -> true;
  54. primetest[{a:int,.b},s:int,k:int]::k%a=0 -> false;
  55. primetest[{a:int,.b},s:int,k:int] -> primetest[b,s,k];
  56.  
  57. nprime[2000] -> 17389
  58. Time taken on LC III: 7079 ticks
  59.  
  60.    Although the above (ReWrite) example has everything clearly typed, and tail recursion keeps the stack use very low, there is a problem that the Pascal version (see below) doesn't share - in the third line of primeaux,
  61.  
  62. primeaux[l:lis,s:int,n:int,k:int]:primetest[l,s,k] -> primeaux[{.l,k},s,n-1,k+1];
  63.  
  64. the parameter l is used in the condition (as well as on the right hand side), which because of unique references means that the whole list of prime found so far has to be copied each time through the loop.
  65.    The following version avoids this problem by passing the whole list to primetest, which doesn't just dispose of the primes that it has tested against so far, but keeps them and returns the complete list of results as well as the result for whether the new number is prime or not. primeaux2 is 'glue' code that takes the result from primetest and adds the new number to the list or not accordingly.
  66.    Note: that this code makes use of some of the more unusual feature of ReWrite:
  67.    - primetest returns 2 results, as an arbitrary number of results can be returned;
  68.    - the list of primes is not passed as an actual list to primetest but it turned into a lot of extra arguments, and because the argument list ends with a .b, this picks up all the primes and puts them into b. This improves the code speed slightly.
  69.  
  70. nprime[n:int] -> primeaux[{},0,n,2];
  71.  
  72. (* primeaux[primes found so far, sqrt, number found, this try] *)
  73. primeaux[l:lis,s:int,0,k:int] -> k-1;
  74. primeaux[l:lis,s:int,n:int,k:int]::k>s*s -> primeaux[l,s+1,n,k];
  75. primeaux[l:lis,s:int,n:int,k:int] -> primeaux2[primetest[s,k,{},.l],s,n,k];
  76.  
  77. (* primeaux2[primes found so far, is prime?, sqrt, number found, this try] *)
  78. primeaux2[l:lis,false,s:int,n:int,k:int] -> primeaux[l,s,n,k+1];
  79. primeaux2[l:lis,true,s:int,n:int,k:int] -> primeaux[{.l,k},s,n-1,k+1];
  80.  
  81. (* primeaux2[sqrt, this try, list of primes checked, primes unchecked] *)
  82. primetest[s:int,k:int,l:lis] -> l,true;
  83. primetest[s:int,k:int,l:lis,a:int,.b]::a>s -> {.l,a,.b},true;
  84. primetest[s:int,k:int,l:lis,a:int,.b]::k%a=0 -> {.l,a,.b},false;
  85. primetest[s:int,k:int,l:lis,a:int,.b] -> primetest[s,k,{.l,a},.b];
  86.  
  87. nprime[2000] -> 17389
  88. Time taken on LC III: 134 ticks - better than a 50-fold improvement!
  89.  
  90.    It is hoped that some future version or ReWrite will be able to do this sort of code transformation automatically as an optimisation, however that is some way off.
  91.  
  92.    Just for an example of how the typing helps, the above example with all the type information removed takes much longer (so putting in all those ints is worth it):
  93.  
  94. nprime[2000] -> 17389
  95. Time taken on LC III: 556 ticks
  96.  
  97.    Here is another implementation of the same algorithm, using features new to ReWrite 0.2.5 (the unrestricted use of splice on the left)
  98.    This version keeps track of four values:
  99.      * the list of primes less than or equal to the square root of the current number (this is the list to check for divisors in),
  100.      * the list of other primes found so far,
  101.      * the number of primes found so far,
  102.      * the current number being checked.
  103.  
  104. nprime[n:int] -> primeaux[{},{},n,2];
  105.  
  106. (* primeaux[(primes found so far <= sqrt[k]), (primes found so far > sqrt[k]), number found, this try] *)
  107. (* found as many primes as we want, so finished *)
  108. primeaux[l1:lis,l2:lis,0,k:int] -> k-1;
  109. (* update the list of primes <= sqrt[k] if necessary *)
  110. primeaux[l1:lis,{s,.l2},n:int,k:int]::k>=s*s -> primeaux[{.l1,s},l2,n,k];
  111. (* not prime if and only if one of the primes <= sqrt[k] divides k *)
  112. primeaux[{.a,b:int,.c},l2:lis,n:int,k:int]::k%b=0 -> primeaux[{.a,b,.c},l2,n,k+1];
  113. (* otherwise prime, so add to list *)
  114. primeaux[l1:lis,l2:lis,n:int,k:int] -> primeaux[l1,{.l2,k},n-1,k+1];
  115.  
  116. nprime[2000] -> 17389
  117. Time taken on LC III: 108 ticks
  118.  
  119.    Just for a comparison, here is a Pascal program using the same algorithm:
  120.  
  121.    function nprime (n: longint): longint;
  122.  
  123.       var
  124.          s, k, i, t: longint;
  125.          f: boolean;
  126.          a: array[0..2000] of longint;
  127.  
  128.    begin
  129.       s := 0;
  130.       k := 2;
  131.       i := 0;
  132.       while i < n do
  133.          begin
  134.             while s * s < k do
  135.                s := s + 1;
  136.             t := 0;
  137.             f := true;
  138.             while (t < i) and f and (a[t] <= s) do
  139.                begin
  140.                   f := (k mod a[t]) <> 0;
  141.                   t := t + 1;
  142.                end;
  143.             if f then
  144.                begin
  145.                   a[i] := k;
  146.                   i := i + 1;
  147.                end;
  148.             k := k + 1;
  149.          end;
  150.       nprime := k - 1;
  151.    end;
  152.  
  153. nprime(2000) -> 17389
  154. Time taken on LC III: 32 ticks
  155.  
  156.    This is much faster, but longer and (I think) has less readable code.
  157.  
  158. atoi2
  159.  
  160.    This converts strings to integers
  161.    Note that atoi2  is not the version or atoi used internally, this version has been updated to use the new character type.
  162.  
  163. atoi2[.x] -> atoixx[xatoi[.x]];
  164.  
  165. atoixx[x:int] -> x;
  166. atoixx[.x] -> "error - not a number";
  167.  
  168. xatoi["-",.n] -> xnegx[xatoi[.n]];
  169. xatoi["$",.a] -> xatoih[0,.a];
  170. xatoi["%",.a] -> xatoib[0,.a];
  171. xatoi[x:char,.a]::xisdigit[x] -> xatoix[0,x,.a];
  172. xatoi[.a] -> {},.a;
  173.  
  174. xnegx[{},.rest] -> {},.rest;
  175. xnegx[a:int,.rest] -> -a,.rest;
  176.  
  177. xatoix[x:int,d:char,.n]::xisdigit[d] -> xatoix[10*x+d:int-"0":int,.n];
  178. xatoix[x:int,.n] -> x,.n;
  179.  
  180. xatoih[x:int,d:char,.n]::xisdigit[d] -> xatoih[16*x+d:int-"0":int,.n];
  181. xatoih[x:int,d:char,.n]::d>="A" & d<="F" -> xatoih[16*x+10+d:int-"A":int,.n];
  182. xatoih[x:int,d:char,.n]::d>="a" & d<="f" -> xatoih[16*x+10+d:int-"a":int,.n];
  183. xatoih[x:int,.n] -> x,.n;
  184.  
  185. xatoib[x:int,"0",.n] -> xatoib[2*x,.n];
  186. xatoib[x:int,"1",.n] -> xatoib[2*x+1,.n];
  187. xatoib[x:int,.n] -> x,.n;
  188.  
  189. xisdigit[d:char] -> d>="0" & d<="9";
  190.  
  191.